#include "Mesh.hpp"
#include "Vec2.hpp"
#include "Mat4.hpp"
#include <algorithm>
#include <set>
#include "Algorithm.hpp"
#include "tiny_vector.hpp"
#include <list>
#include <boost/graph/adjacency_list.hpp>
//#include <boost/unordered_map.hpp>
class Box3;
class PolyMesh;
class EdgeMesh;
class CreaseStructure;
class MeshAdjacency;
namespace MeshAlgorithm
{
   //using namespace boost::graph;
   //using namespace boost;
   //typedef adjacency_list<mapS, vecS, undirectedS> EdgeGraph;
   //
   //void BuildEdgeGraph(EdgeGraph&              aGraph,
   //                    const std::vector<Edge> aEdges,
   //                    int                     aVertexCount);
   typedef std::vector<int> EdgeCycle;
   typedef std::list<EdgeCycle> EdgeCycleList;
   void FindCycles(const std::vector<Edge> aEdges,
                   int                     aMaxEdgeCount,
                   EdgeCycleList&          aCycles);

   

   typedef tiny_vector<size_t, 3> AdjacentFaces;
   typedef std::map<Edge, AdjacentFaces> AdjacencyMap;
   //typedef boost::unordered_map<Edge, AdjacentFaces> AdjacencyMap;
   void MakeAdjacencyMap(const FaceList& aFaces,
                         AdjacencyMap&   aAdjacencyMap);

   void FillRegion(MeshAdjacency&          aAdjacency,
                   const std::vector<int>& aStartFaces,
                   std::vector<int>&       aRegionFaces);

   void FillRegion(AdjacencyMap&           aAdjacencyMap,
                   const FaceList&         aFaces,
                   const std::vector<int>& aStartFaces,
                   std::vector<int>&       aRegionFaces);
   void CreaseEdgePatch(Mesh&          aMesh,
                        MeshAdjacency& aAdjacency,
                        Edge           aEdge,
                        EdgeList&      aEdgePatch);
   void EdgeMaterials(Mesh&             aMesh,
                      MeshAdjacency&    aAdjacency,
                      Edge              aEdge,
                      std::vector<int>& aMaterials);
   void GetBorderEdges(const Mesh&      aMesh,
                       const IndexList& aFaces,
                       EdgeList&        aBorderEdges);
   void GetEdgeVertices(const EdgeList& aEdges,
                        IndexList&      aVertices);
   //void FillRegion(AdjacencyMap&           aAdjacencyMap,
   //                const FaceList&         aFaces,
   //                const std::vector<Edge>& aBorders,
   //                const std::vector<int>& aStartFaces,
   //                std::vector<int>&       aRegionFaces);

   void FindFaces(const FaceList&         aFaces,
                  const std::vector<int>& aVerts,
                  std::vector<int>&       aSelFaces);

   //void FindCreaseRegions(const Mesh&              aMesh,
   //                       std::list<RegionCrease>& aCreases);

   //void FindCycles(PolyMesh&         aMesh,
   //                std::vector<int>& aSelVerts,
   //                std::list<std::pair<RegionInterface, IndexList> >&     aCycles);

   //void FixCycle(Mesh&             aMesh,
   //              std::vector<int>& aEdges,
   //              RegionInterface   aInterface);

   bool FixCycle(Mesh&            aMesh,
                 CreaseStructure& aCreases,
                 int              aLoopIndex);

   bool DetatchInterface(Mesh&            aMesh,
                         CreaseStructure& aCreases,
                         int              aInterfaceIndex,
                         int              aFillMaterial);

   bool DetatchInterface2(Mesh&            aMesh,
                          CreaseStructure& aCreases,
                          int              aInterfaceIndex,
                          int              aFillMaterial);
   void DetatchInterface3(Mesh&            aMesh,
                          MeshAdjacency&   aAdjacency,
                          CreaseStructure& aCreases,
                          int              aPatchIndex,
                          int              aFillMaterial);

   void DetatchInterface4(Mesh&            aMesh,
                          MeshAdjacency&   aAdjacency,
                          const IndexList& aFaces,
                          const EdgeList&  aEdges,
                          int              aFillMaterial);

   bool DetatchInterface2(Mesh&                aMesh,
                          std::list<IndexList> aCreaseLoops,
                          RegionInterface      aInterface,
                          int                  aFillMaterial);

   bool FixCycle(Mesh&            aMesh,
                 CreaseStructure& aCreases,
                 int              aLoopIndex,
                 RegionInterface  aInterface);

   void FindCycles(PolyMesh&                     aMesh,
      CreaseStructure&              aCreases,
                   std::vector<int>&             aSelVerts,
                   std::list<std::pair<RegionInterface, IndexList> >& aCycles);


   class VertexFaceLinks;

   int GetVertexStar(int              aVertex,
                     const Mesh&      aMesh,
                     VertexFaceLinks& aLinks,
                     int*             aIndices);

   class VertexFaceLinks
   {
   public:
      VertexFaceLinks(int         aMaxFaces,
                      const Mesh& m);

      friend int MeshAlgorithm::GetVertexStar(int              aVertex,
                                              const Mesh&      aMesh,
                                              VertexFaceLinks& aLinks,
                                              int*             aIndices);
      // Returns faces surrounding vertex
      int GetVertexFaces(int              aVertex,
                         VertexFaceLinks& aLinks,
                         int*             aFaces)
      {
         int outInd=0;
         int index = aVertex * mMaxFaces;
         for (int i = 0; i < mMaxFaces; ++i)
         {
            if (mData[index] == -1) break;
            aFaces[outInd++] = mData[index++];
         }
         return outInd;
      }  
      // returns all faces sharing an edge
      int GetEdgeFaces(const Edge&      aEdge,
                       Mesh&            aMesh,
                       VertexFaceLinks& aLinks,
                       int*             aFaces)
      {
         int outInd=0;
         int index = aEdge.first * mMaxFaces;
         for (int i = 0; i < mMaxFaces; ++i)
         {
            if (mData[index] == -1) break;
            int triIndex = mData[index++];
            Face& f = aMesh.faces[triIndex];
            if (f.vertex[0] == aEdge.second
            || f.vertex[1] == aEdge.second
            || f.vertex[2] == aEdge.second)
            {
               aFaces[outInd++] = triIndex;
            }
         }
         return outInd;
      }  

   private:
      int               mMaxFaces;
      std::vector<int>  mData;

      void InsertLink(int aFace, int aVertex)
      {
         int index = aVertex * mMaxFaces;
         for (int i = 0; i < mMaxFaces; ++i)
         {
            if (mData[index] == -1)
            {
               mData[index] = aFace;
               return;
            }
            ++index;
         }
         std::cerr << "Too many faces.\n";
         exit(1);
      }
   };

   void MakeAdjacencyMap(const VertexFaceLinks& aLinks,
                         const Mesh&            aMesh,
                         AdjacencyMap&          aAdjacencyMap);

   void RemoveFacelessVertices(Mesh& aMesh);
   
   class SelectMaterial
   {
      public:
         SelectMaterial(int aMaterial) : mMaterial(aMaterial) {}
         bool operator()(Face& aFace)
         {
            return aFace.materials[0] == mMaterial
               || aFace.materials[1] == mMaterial;
         }
         int mMaterial;
   };

   class SelectMaterials
   {
   public:
      template <typename ITER>
      SelectMaterials(ITER aBegin, ITER aEnd)
      {
         mMaterials.insert(aBegin, aEnd);
      }
      bool operator()(Face& aFace)
      {
         if (mMaterials.find(aFace.materials[0]) != mMaterials.end()
            || mMaterials.find(aFace.materials[1]) != mMaterials.end())
         {
            return true;
         }
         return false;
      }
      std::set<int>  mMaterials;
   };

   class SelectTwoMaterials
   {
   public:
      template <typename ITER>
      SelectTwoMaterials(ITER aBegin, ITER aEnd)
      {
         mMaterials.insert(aBegin, aEnd);
      }
      bool operator()(Face& aFace)
      {
         if (mMaterials.find(aFace.materials[0]) != mMaterials.end()
            && mMaterials.find(aFace.materials[1]) != mMaterials.end())
         {
            return true;
         }
         return false;
      }
      std::set<int>  mMaterials;
   };

   template <typename FUNC>
   class SelectInverse
   {
      public:
         SelectInverse(FUNC aFunc) : mFunc(aFunc) { }
         bool operator()(Face& aFace)
         {
            return !mFunc(aFace);
         }
         FUNC mFunc;
   };
   class VertexSelectionCriteria
   {
      public:
         VertexSelectionCriteria(const std::vector<int>& aVerts)
         {
            verts.insert(aVerts.begin(), aVerts.end());
         }
         bool operator()(Face& aFace) const
         {
            return verts.find(aFace.vertex[0]) != verts.end()
               && verts.find(aFace.vertex[1]) != verts.end()
               && verts.find(aFace.vertex[2]) != verts.end();
         }
         std::set<int> verts;
   };
   class FaceSelectionCriteria
   {
   public:
      FaceSelectionCriteria(std::vector<int>& aFaces) : mFaces(aFaces) 
      {
         mIndex = 0;
         std::sort(mFaces.begin(), mFaces.end());
         mFaces.erase(std::unique(mFaces.begin(), mFaces.end()), mFaces.end());
         mNext = mFaces.begin();
      }
      FaceSelectionCriteria(const FaceSelectionCriteria& aSrc) 
      {
         mFaces = aSrc.mFaces;
         mNext = mFaces.begin();
         mIndex = 0;
      }
      bool operator()(Face& aFace)
      {
         int index = mIndex++;
         bool remove = false;
         if (mNext == mFaces.end()) return false;
         if (index == *mNext)
         {
            remove = true;
            ++mNext;
         }
         return remove;
      }
      int mIndex;
      std::vector<int>::iterator mNext;
      std::vector<int>  mFaces;
   };

   template <typename FUNC>
   SelectInverse<FUNC> Inverse(FUNC aFunc) { return SelectInverse<FUNC>(aFunc); }

   template <typename RemoveCriteria>
   void RemoveFaces(Mesh&          aMesh,
                    RemoveCriteria c)
   {
      //FaceList::iterator newEnd = 
         //std::remove_if(aMesh.faces.begin(), aMesh.faces.end(), c);
      typedef std::vector<Face>::iterator Iter;
      Iter first = aMesh.faces.begin();
      Iter last = aMesh.faces.end();
      Iter dest = first;
      for (; first != last; ++first)
      {
         if (!c(*first))
         {
            if (dest != first)
            {
               *dest = *first;
            }
            ++dest;
         }
      }
      aMesh.faces->erase(dest, last);
      RemoveFacelessVertices(aMesh);
   }

   template <typename RemoveCriteria>
   void RemoveFacesKeepVerts(Mesh&          aMesh,
                             RemoveCriteria c)
   {
      FaceList::iterator newEnd = 
         std::remove_if(aMesh.faces.begin(), aMesh.faces.end(), c);
      aMesh.faces->erase(newEnd, aMesh.faces.end());
   }

   bool CheckValidMesh(const PolyMesh& aMesh);
   bool CheckValidMesh(const Mesh& aMesh);

   void CheckValidFaces(Mesh& aMesh);

   void PrintEdgeInfo(Mesh& aMesh);

   void PrintMeshInfo(Mesh& aMesh);

   void SplitMaterials(Mesh&           aMesh,
                       std::list<Mesh>& aMeshParts);

   void MakeManifold(Mesh& aMesh);

   // Returns the vertices surrounding a vertex
   inline int GetVertexStar(int              aVertex,
                            const Mesh&      aMesh,
                            VertexFaceLinks& aLinks,
                            int*             aIndices)
   {
      int vertexTotal(0);
      int index = aVertex * aLinks.mMaxFaces;
      for (int i = 0; i < aLinks.mMaxFaces && aLinks.mData[index] != -1; ++i)
      {
         int faceIndex = aLinks.mData[index];
         const Face& f = aMesh.faces[faceIndex];
         if (f.vertex[0] != aVertex) aIndices[vertexTotal++] = f.vertex[0];
         if (f.vertex[1] != aVertex) aIndices[vertexTotal++] = f.vertex[1];
         if (f.vertex[2] != aVertex) aIndices[vertexTotal++] = f.vertex[2];
         ++index;
      }
      Algorithm::ShellSort(aIndices, vertexTotal);
      return std::unique(aIndices, aIndices + vertexTotal) - aIndices;
   }

   //inline int GetVertexStarEdge(int              aVertex1,
   //                             int              aVertex2,
   //                             const Mesh&      aMesh,
   //                             VertexFaceLinks& aLinks,
   //                             int*             aIndices)
   //{
   //   int vertexTotal(0);
   //   int index = aVertex1 * aLinks.mMaxFaces;
   //   for (int i = 0; i < aLinks.mMaxFaces && aLinks.mData[index] != -1; ++i)
   //   {
   //      int faceIndex = aLinks.mData[index];
   //      const Face& f = aMesh.faces[faceIndex];
   //      if (f.vertex[0] != aVertex1) aIndices[vertexTotal++] = f.vertex[0];
   //      if (f.vertex[1] != aVertex1) aIndices[vertexTotal++] = f.vertex[1];
   //      if (f.vertex[2] != aVertex1) aIndices[vertexTotal++] = f.vertex[2];
   //      ++index;
   //   }
   //   Algorithm::ShellSort(aIndices, vertexTotal);
   //   return std::unique(aIndices, aIndices + vertexTotal) - aIndices;
   //}

   void SmoothMesh(Mesh&            aMesh,
                   VertexFaceLinks& aLinks,
                   float            aSmoothFactor);

   void ComputeMeshParameters(const VertexList& aVerts,
                              Box3&             aBounds);
struct NonManifoldEdge
{
   int verts[2];
   int face_count;
};
   void ComputeNonManifoldEdges(const Mesh&                   aMesh,
                                std::vector<NonManifoldEdge>& aEdges);

   void ComputeMaterialNonManifoldEdges(const Mesh&                   aMesh,
                                        std::vector<NonManifoldEdge>& aEdges);

   void AverageSmooth(Mesh& aInMesh,
                      int   aIterations);
   void DistanceSmooth(Mesh& aInMesh,
                       int   aIterations);
   void CurvatureSmooth(Mesh& aInMesh,
                        int aIterations);

   void ComputeEdges(std::vector<Face>& aEdgeFaces,
                     std::vector<Edge>& aEdges);

   void LeipaRefine(float aAlpha);

   void FlipMaterials(Mesh& aMesh);

   void RefineMesh(EdgeMesh& aMesh,
                   float     aLength);

   void RefineMeshRatio(EdgeMesh& aMesh,
                        float     aRatio);

   void OrientMaterial(Mesh& aMesh,
                       int   aMaterial);

   void SplitMesh(Mesh& aMesh);

   void FindDuplicateFaces(const Mesh&              aMesh,
                           std::vector<Face>& aFaces);

   void CleanBadFaces(Mesh& aMesh);

   bool RayTriangleIntersect(Vec3 ray_origin, Vec3 ray_direction,
      Vec3 vert0, Vec3 vert1, Vec3 vert2,
      float& t, float& u, float& v);

   void FindRayHits(const Mesh& aMesh,
                    Vec3        aOrigin,
                    Vec3        aDirection,
                    std::vector<std::pair<float, int> >& aHitFaces);

   void FindRayHits(const PolyMesh& aMesh,
                    Vec3        aOrigin,
                    Vec3        aDirection,
                    std::vector<std::pair<float, int> >& aHitPolys);

   void FindIntersectingFaces(const Mesh&       aMesh,
                              std::vector<int>& aFaces);
   void DivideArea(const Mesh&                   aMesh,
                   std::list<std::vector<int> >& aFaceGroups);

   void BoxSelectVertices(std::vector<Vec3>& aVertexList,
                          Mat4               aTransform,
                          Vec2               aMin,
                          Vec2               aMax,
                          std::vector<int>&  aInside);

   void Subdivide(PolyMesh& aMesh);

   struct TetPair
   {
      boost::array<int, 2> tetTips;
      boost::array<int, 3> verts;
   };

   void GetTetPairs(PolyMesh&             aMesh,
                    std::vector<TetPair>& aTetPairs);

   void ExtractMatPoints(Mesh&                  aMesh,
                         std::vector<MatPoint>& aPoints);
}
